The present invention relates to a two-dimensional round-robin scheduling method. In particular, the present invention relates to a two-dimensional round-robin scheduling method with multiple selection of input and output buffered switch.
Generally, the performance of input-buffered switches is not as good as that of output-buffered switches due to HOL (head of line) blocking phenomenon. However, the output-buffered switch is not appropriate for high-speed link since operating speed of switch memory fabric or output buffer should be faster than N times of link operating speed. On the contrary, input-buffered switches are appropriate for high-speed link because speed of switch memory fabric such as crossbar and Batcher-banyan is same as link operating speed.
There is an architecture for mitigating HOL blocking phenomenon and it is the multiple input buffer architecture in which each input port uses a number of buffers for an output port. In this architecture, there are N input ports and each input port is connected with N queues for output ports. Therefore, there are N2 input queues in total. However, since Nxc3x97N switches have N input links, only N queues are selected among the N2 queues and it is called contention problem. There are several methods proposed to solve the contention problem and they are PIM (parallel iterative method), SLIP, 2DRR (two-dimensional round-robin) method, and TRM (time reservation method).
PIM method consists of request step, grant step, and accept step. At request step, N2 input queues send requests to output ports. At grant step, output port randomly grants a request among received requests and notifies the result to each input port. Since an output port may receive a number of grants from an input port, only one grant is randomly selected and accepted among received grants.
Even though performance of PIM method is improved as request step, grant step, and accept step are repeated, it is fairly difficult to apply PIM method to high-speed applications because random operations are required for grant step and accept step.
SLIP method does not use probability functions. SLIP method was proposed at xe2x80x9cScheduling cells in an input-queued switchxe2x80x9d, Electronics letters, Vol. 29, No. 25, December 1993, N. McKeown et al. and also at U.S. Pat. No. 5,500,858, N. McKeown. SLIP method utilizes round-robin scheme instead of random operations at grant step and accept step. That is, round robin pointer is used instead of the random operations. If current round-robin pointer value is i, first input port after ith input port is granted among requests received. The value of round-robin pointer is increased by one only if the grant is accepted by input port. In accept step of input port, round-robin pointer is used as well.
However, SLIP method is problematic in that synchronization problem is caused. That is, a number of output ports may grant an identical input port. In order to remove the synchronization problem, SLIP algorithm has to be repeated. In the worst case, the algorithm has to be repeated N times to converge in case that Nxc3x97N switch is used. In addition, if a number of input and output ports increases, a number of requests and grants that needs to be searched at grant step and accept step increases as well. That is, if a number of input and output ports increases, it is difficult to apply SLIP method to high-speed applications.
2DRR method is proposed at xe2x80x9cTwo-dimensional round-robin schedulers for packet switches with multiple input queuesxe2x80x9d, IEEE/ACM transactions on networking, Vol. 2, No. 5, October 1994, R. O. LaMaire et al. and also at U.S. Pat. No. 5,299,190, R. O. LaMaire et al. In 2DRR method, N2 requests are represented by Nxc3x97N matrix. Only N search steps are required to determine a request to be transmitted. The service fairness of 2DRR method is equivalent to the service fairness that SLIP in iterated N times.
In the technical paper stated above, basic 2DRR algorithm searches request matrix in sequence defined by pattern sequence matix and determines a request to be transmitted. Enhanced 2DRR algorithm proposed by the technical paper shows performed improvement for specified traffic patterns. If a number of input and output ports increases, it is difficult to apply 2DRR method to high-speed applications because search steps of the algorithm are also increased.
TRM is proposed at xe2x80x9cInput and Output queuing ATM switch architecture with spatial and temporal slot reservation controlxe2x80x9d, Electronics letters, Vol. 28, No. 1, January 1992, H. Obara et al. TRM utilizes input and output buffered switch that grouped input and output ports are used. Grouping input and output ports reduces number of queues for each input port and therefore number of requests used for contention is also decreased. A grouped input port selects a number of requests to prevent performance deterioration of switch. Overall performance of switch is improved by the statistical multiplexing gain due to the grouping.
In the paper proposing TRM, time information is used in contention control. When input buffer module sends requests to contention control module, contention control module sets transmission time and then notifies the time to input buffer module. Therefore, in case of large-scale switch, it is difficult to perform high-speed operation since the amount of time information is increased. Also, it is difficult to perform high-speed operation since number of input and output links is increased as number of input and output ports is increased.
C. Lund et. al disclosed a method at U.S. Pat. No. 5,517,495. The method is similar with the TRM and time information is used for contention control and service fairness is improved. In the invention, a request for a cell that waits for the longest time is transmitted to contention control module in consideration with priorities of output ports. Contention control module grants the longest waiting one among the received requests and notifies the result to input ports. Each input port is able to receive multiple grants from a number of output ports at the same time. Each input port accepts the longest waiting one among the received grants. Even though the method proposed by the invention U.S. Pat. No. 5,517,495 shows better performance than PIM method and SLIP method, it is difficult to apply the method to high-speed applications since time information should be sent in grant and accept steps and a minimum value is searched in the time information.
A two-dimensional round-robin scheduling method with multiple selection is provided. The two-dimensional round-robin scheduling method in accordance with an embodiment of the present invention employs input buffer modules, output buffer modules, a space division switching module and a contention control module. The input buffer module has input ports and queues. The output buffer module has output ports and queues. The space division switching module has switching planes. The space division switching module is connected with the input buffer modules through links and connected with the output buffer modules through links. The two-dimensional round-robin scheduling method in accordance with an embodiment of the present invention includes following steps. First step is for detecting whether a request signal is received from the input buffer module and building mxc3x97m request matrix r(i,j), i,j=1, . . . , m. Second step is for setting mxc3x97m search pattern matrix, d(i,j), i,j=1, . . . , m. The search pattern matrix describes search sequence, S=1, . . . , m. Third step is for initializing elements of mxc3x97m allocation matrix a(i,j), i,j=1, . . . , m. The allocation matrix contains information whether transmission request is accepted and which switching plane is used in the transmission. Fourth step is for examining a request matrix in accordance with the search sequence of search pattern matrix and finding r(i,j) that requests transmission. Fifth step is for setting a(i,j) for all (i,j) pairs found in the fourth step so that elements of allocation matrix at ith row have different values in range from 1 to n and elements of allocation matrix at jth column have different values in range from 1 to n. Sixth step is for repeating the fourth step and the fifth step as the search sequence S is increased from 1 to m by 1.
Preferably, the request matrix at the first step has r(i,j)=1 if there is a cell to be transmitted from ith input buffer module to jth output buffer module and has r(i,j)=0 if there is not any cell to be transmitted from ith input buffer module to jth output buffer module.
Preferably, the fifth step for all (i,j) pairs which are found in the fourth step includes following sub-steps. First sub-step is for initializing variable k=1 where the variable k indicates switching plane number. Second sub-step is for determining whether elements of allocation matrix at ith row and elements of allocation matrix at jth column are not equal to value of the variable k. Third sub-step is for setting a(i,j)=k and finishing the fifth step if the condition at the second sub-step is satisfied. Fourth sub-step is either for increasing k by 1 and returning to the second sub-step if the condition at the second sub-step is not satisfied and k is smaller than n or for maintaining a(i,j) at the initialized state and finishing the fifth step if the condition at the second sub-step is not satisfied and k is equal to n.
Preferably, the fifth step for all (i,j) pairs which are found in the fourth step includes following sub-steps. First sub-step is for setting a(i,j)=1 if elements of allocation matrix at ith row and elements of allocation matrix at jth column are all zero. Second sub-step is for setting a(i,j)=k if elements of allocation matrix at ith row and elements of allocation matrix at jth column have all integers from 1 to kxe2x88x921 and all the elements of allocation matrix at ith row and all the elements of allocation matrix at jth column are not k.
Preferably, the fifth step sets a(i,j) using row index vector Wp (p=1, . . . , n) and column index vector Cp (p=1, . . . , n). The row index vector Wp indicates that elements of allocation matrix at each row have a value of p. The column index vector Cp indicates that elements of allocation matrix at each column have a value of p.
Preferably, the fifth step includes following sub-steps. First sub-step is for initializing the row index vector Wp=(wp(1), . . . , wp(m)) and the column index vector Cp=(cp(1), . . . , cp(m)), p=1, . . . , n. Second sub-step is for determining whether wk(i)=0 and ck(j)=0. Third sub-step is for setting a(i,j)=k, wk(i)=1 and ck(j)=1 and finishing the fifth step if condition of the second sub-step is satisfied. Fourth sub-step is either for increasing k by 1 and returning to the second sub-step if the condition at the second sub-step is not satisfied and k is smaller than n or for maintaining a(i,j) at the initialized state and finishing the fifth step if the condition at the second sub-step is not satisfied and k is equal to n. The second sub-step, the third sub-step, and the fourth sub-step are applied to all (i,j) pairs.